package com.fr.lintcode;

public class Q511 {
	/**
     * @param head: a ListNode
     * @param v1: An integer
     * @param v2: An integer
     * @return: a new head of singly-linked list
     */
    public ListNode swapNodes(ListNode head, int v1, int v2) {
        // write your code here	
    	ListNode p1 = null;
    	ListNode p2 = null;
    	ListNode n1 = null;
    	ListNode n2 = null;
    	ListNode tmp = head;
    	ListNode parent = null;
    	while(tmp != null) {
    		if(tmp.val == v1) {
    			p1 = parent;
    			n1 = tmp;
    		}else if(tmp.val == v2) {
    			p2 = parent;
    			n2 = tmp;
    		}
    		parent = tmp;
    		tmp = tmp.next;
    	}
    	if(n1 == null || n2 == null) {
    		return head;
    	}
    	ListNode tmp1 = n1.next;
		ListNode tmp2 = n2.next;
		
    	if(p1 == null) {
    		if(p2 == n1) {
    			n2.next = n1;
    			n1.next = tmp2;
    		}else {
    			n2.next = tmp1;
        		n1.next = tmp2;
        		p2.next = n1;
    		}
    		
    		return n2;
    	}else if(p2 == null) {
    		if(p1 == n2) {
    			n1.next = n2;
    			n2.next = tmp1;
    		}else {
    			n2.next = tmp1;
        		n1.next = tmp2;
        		p1.next  = n2;
    		}
    		
    		return n1;
    	}else if(p1 == n2){
    		n1.next = n2;
    		p2.next = n1;
    		n2.next = tmp1;
    	}else if(p2 == n1){
    		n2.next = n1;
    		n1.next = tmp2;
    		p1.next  = n2;
    	}else {
    		n2.next = tmp1;
    		n1.next = tmp2;
    		p1.next = n2;
    		p2.next = n1;
    	}
    	return head;
    }
}
